package hash;

import java.util.Map;
import java.util.NoSuchElementException;

/**
 * 基于开散列方式下整型哈希表的实现
 *
 * @author 是阿秋啊
 * @date 2022/03/23 14:57
 **/
public class MyHashMap {
    private class Node {
        // 对key求哈希运算
        int key;
        int value;
        Node next;

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 记录存入的键值对个数
    private int size;
    // 默认哈希表长度
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final double LOAD_FACTOR = 0.75;
    // 取模数，用于获取key索引
    private int M;
    // 实际存储的数组
    private Node[] data;

    public MyHashMap() {
        // 默认无参构造数组长度为默认值
        this(DEFAULT_CAPACITY);
    }

    public MyHashMap(int initCap) {
        // 定义初始长度
        this.M = initCap;
        this.data = new Node[initCap];
    }

    // 哈希函数
    public int hash(int key) {
        // 获取索引
        return Math.abs(key) % M;
    }

    // 在当前的哈希表添加一个键值对 key = value
    public int put(int key, int value) {
        // 1.先获取key值对应的索引
        int index = hash(key);
        // 2.在哈希表中查找是否存储过
        for (Node x = data[index]; x != null; x = x.next) {
            if (x.key == key) {
                //key存在，修改value值
                int oldVal = x.value;
                x.value = value;
                return oldVal;
            }
        }
        // 走到这里则表示哈希表中没有存储key值
        // 使用头插法将新key插入
        Node node = new Node(key, value, data[index]);
        data[index] = node;
        size++;
        // 4.添加一个元素后查看哈希表是否需要扩容
        if (data.length * LOAD_FACTOR <= size) {
            // 扩容
            resize();
        }
        return value;
    }

    // 哈希表扩容
    private void resize() {
        Node[] newData = new Node[data.length << 1];
        this.M = newData.length;
        for (Node datum : data) {
            if (datum != null) {
                // 对应的链表不为空
                // 进行对应的链表遍历
                for (Node x = datum; x != null; ) {
                    // 此处不在for循环中写x递进条件，是因为x会指向新数组的节点，next会发生变化
                    // 暂存一下后继节点
                    Node next = x.next;
                    // 新数组的头插
                    int newIndex = hash(x.key);
                    x.next = newData[newIndex];
                    newData[newIndex] = x;
                    // 继续进行下一个节点的搬移操作
                    x = next;
                }
            }
        }
        data = newData;
    }

    /**
     * 删除哈希表中key对应的节点
     * 返回删除前的value
     *
     * @param key
     * @return
     */
    public int remove(int key) {
        int index = hash(key);
        // 判断头节点是否是待删除的节点
        Node head = data[index];
        if (head.key == key) {
            int val = head.value;
            data[index] = head.next;
            head.next = head = null;
            size--;
            return val;
        }
        // 此时不是头节点
        Node prev = head;
        // 此时不需要判断头节点
        while (prev.next != null) {
            // prev为待删除值的前驱节点
            if (prev.next.key == key) {
                Node cur = prev.next;
                int val = cur.value;
                prev.next = cur.next;
                cur.next = cur = null;
                return val;
            }
            prev = prev.next;
        }
        // 走到此时说明哈希表中没有key的节点
        throw new NoSuchElementException("no such key! cannot remove!");
    }

    // 判断哈希表中是否含有key的节点
    public boolean containsKey(int key) {
        int index = hash(key);
        for (Node x = data[index]; x != null; x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }

    // 判断含有值为value的节点
    public boolean containsValue(int value) {
        // 不同于查找key，查找value需要遍历整个哈希表
        for (Node datum : data) {
            for (Node x = datum; x != null; x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }
}
